To solve an elliptic PDE eigenvalue problem in practice, typically the finite element discretisation is used. From approximation theory it is known that only the smaller eigenvalues and their corresponding eigenfunctions can be well approximated by the finite element discretisation because the approximation error increases with increasing size of the eigenvalue. The number of well approximable eigenvalues or eigenfunctions, however, is unknown. In this work asymptotic estimates of these quantities are derived. For example, it is shown that for three-dimensional problems under certain smoothness assumptions on the data only the smallest $\Theta (N^{2/5})$ eigenvalues and only the eigenfunctions associated to the smallest $\Theta (N^{1/4})$ eigenvalues can be well approximated by the finite element discretisation, when the $N$-dimensional finite element spaces of piecewise affine functions with uniform mesh refinement are used. To solve the discretised elliptic PDE eigenvalue problem and to compute all well approximable eigenvalues and eigenfunctions, a new method is introduced which combines a recursive version of the automated multi-level substructuring (short AMLS) method with the concept of hierarchical matrices (short $\mathcal{H}$-matrices). AMLS is a domain decomposition technique for the solution of elliptic PDE eigenvalue problems where, after some transformation, a reduced eigenvalue problem is derived whose eigensolutions deliver approximations of the sought eigensolutions of the original problem. Whereas the classical AMLS method is very efficient for elliptic PDE eigenvalue problems posed in two dimensions, it is getting very expensive for three-dimensional problems, due to the fact that it computes the reduced eigenvalue problem via dense matrix operations. This problem is resolved by the use of hierarchical matrices. $\mathcal{H}$-matrices are a data-sparse approximation of dense matrices which, e.g., result from the inversion of the stiffness matrix that is associated to the finite element discretisation of an elliptic PDE operator. The big advantage of $\mathcal{H}$-matrices is that they provide matrix arithmetic with almost linear complexity. This fast $\mathcal{H}$-matrix arithmetic is used for the computation of the reduced eigenvalue problem. Beside this, the size of the reduced eigenvalue problem is bounded by a new recursive version of AMLS which further reduces the costs for the computation and the solution of this problem. Altogether this leads to a new method which is well-suited for three-dimensional problems and which allows us to compute a large amount of eigenpair approximations in optimal complexity.
展开▼
